Dynamic Network Flows - Chapter 4: The Vickrey Queuing Model

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\sMid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\deriv}[2][]{\partial_{#1} #2} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\cexittime}[1][e]{A_{#1}} \newcommand{\network}{N} \newcommand{\tauPmin}{\tau_{p_{\min}}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)

$f_e = (f^+_e,f^-_e)$ Vickrey flow if $\ql(0)=0$ and $f^-_e(\theta+\tau_e) = \begin{cases}\nu_e, &\text{if } \ql(\theta) > 0 \\ \min\set{f^+_e(\theta),\nu_e}, &\text{else } \end{cases}$ f.a.a. $\theta \in \IRnn$

⤳ exit/arrival time $\cexittime(\theta) \coloneqq \theta + \tau-e + \frac{1}{\nu_e}\ql(\theta)$

Lemma 4.3: The following are equivalent for $f_e = (f^+_e,f^-_e)$:

$f$ is a Vickrey flow
$f$ satisfies $\ql(0)=0$ and
$\deriv{\ql}(\theta) = \begin{cases} f^+_e(\theta) - \nu_e, &\text{ if } \ql(\theta) > 0 \\ \max\set{f^+_e(\theta) - \nu_e,0}, &\text{ else} \end{cases}$ f.a.a. $\theta \in \IRnn$
$f$ satisfies weak flow-conservation, respects the capacity and satisfies
mmmm$F^-_e(\theta+\tau_e) = F^+_e(\bar\theta)+(\theta-\bar\theta)\nu_e$ for all $\theta \in \IRnn$
where $\bar\theta \coloneqq \max\set{\theta' \leq \theta \sMid \ql(\theta')=0}$
$f$ satisfies $F^-_e(\theta+\tau_e) = \min\set{F^+_e(\theta')+(\theta-\theta')\nu_e \sMid \theta' \leq \theta}$
$f$ satisfies weak flow-conservation, respects the capacity and satisfies
mmmm$F^-_e(\cexittime(\theta)) = F^+_e(\theta)$ for all $\theta \in \IRnn$

Lemma 4.4 $f^+_e: \IR \to \IRnn$ loc. int. with $\supp(f^+_e) \subseteq \IRnn$
mm $\implies \exists f^-_e: \IR \to \IRnn$ loc. int. with $(f^+_e,f^-_e)$ Vickrey flow

Lemma 4.5 $f_e, g_e$ Vickrey flows: $f^+_e(\theta) = g^+_e(\theta)$ f.a.a. $\theta \leq \bar\theta$
mm $\implies f^-_e(\theta) = g^-_e(\theta)$ f.a.a. $\theta \leq \cexittime^f(\bar\theta) = \cexittime^g(\bar\theta)$

(Vickrey) edge-loading mapping: \[\Phi_e: \set{f^+_e \in L^1_{\mathrm{loc}}(\IR) \sMid \supp(f^+_e) \subseteq \IRnn, f^+_e \geq 0} \to L^1_{\mathrm{loc}}(\IR), f^+_e \mapsto f^-_e \text{ s.th. } (f^+_e,f^-_e) \text{ is Vickrey flow}\]

Lemma 4.7: $\Phi_e^{\class{tempstep}{\data{tempstep-classes=57:hl}{T}}}: \set{f^+_e \in L^{\class{tempstep}{\data{tempstep-classes=57:hl}{2}}}(\IR) \sMid \supp(f^+_e) \subseteq \class{tempstep}{\data{tempstep-classes=57:hl}{[0,T]}}, f^+_e \geq 0} \to L^{\class{tempstep}{\data{tempstep-classes=57:hl}{2}}}(\IR), f^+_e \mapsto \Phi_e(f^-_e)$ is sequentially weak-weak-continuous.